package leetcode;/*给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。*/

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class NumIdenticalPairs {
    //使用双重循环嵌套，时间复杂度为O（n^2），当数组较大时，效率较低
//    public static int numIdenticalPairs(int[] nums) {
//        int count = 0;
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                if (nums[i] == nums[j]) {
//                    count++;
//                }
//            }
//        }
//        return count;

    //使用哈希表（如 HashMap）来统计频率，然后计算每个频率对应的好数对数目并求和。
    public static int numIdenticalPairs(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int count = 0;
        for (int x : map.values()) {
            count += x * (x - 1) / 2;
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入数组的长度: ");
        int length = scanner.nextInt();
        int[] nums = new int[length];
        System.out.print("请输入数组元素（用空格分隔）:");
        for (int i = 0; i < length; i++) {
            nums[i] = scanner.nextInt();
        }
        int result = numIdenticalPairs(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println("好数对的数量: " + result);
        scanner.close();
    }
}
